import re
import heapq
from UnionFind import UnionFind
from DisjointSets import *

class Edges:
	def __init__(self, vertex1, vertex2, weight):
		self.vertex1 = vertex1
		self.vertex2 = vertex2
		self.weight = weight
		
class Vertex:
	def __init__(self, value):
		self.value = value

	def __str__(self):
		return self.value

class Grafo:
	
	def __str__(self):
		#Imprime el contenido de los vertices y las aristas
		s = "Vertex -> Edges\n"
		for k, v in self.grafo.iteritems():
			s+= "%s -> %s\n" % (k, v)
		return s
		
	def __init__(self):
		self.grafo = {}
        
	def __init__(self, filePointer):
	#Construye el grafo a partir de parsear el archivo
		self.grafo = {}
	
		for line in filePointer:
			lines = line.replace(' ','').split(':')
			# Guardo el vertice actual
			verticeActual = lines[0]
			if (not self.isVertex(Vertex(verticeActual))):
				self.addVertex(Vertex(verticeActual))
				
			num = ""
			verticeVecino = ""
			cadena = lines[1]
			# Proceso la linea
			for i in range(len(cadena)):
				char = cadena[i]
				if (char == ')'):
					# Agrego arista entre VActual y V que estoy procesando
					x = int(num)
					print "Agrego arista %s , %s , %s" % (verticeActual, verticeVecino, x)
					#self.addEdge(verticeActual, verticeVecino, x)
					self.addEdge( Edges(Vertex(verticeActual), Vertex(verticeVecino), x) )
					print "("+verticeActual +","+ verticeVecino+"," +num+")"
				elif (char == '('):
					num = ""
				elif (char == ','):
					verticeVecino = num
					if (not self.isVertex(Vertex(verticeVecino))):
						#self.addVertex(verticeVecino)
						self.addVertex(Vertex(verticeVecino))
					num = ""
				else:
					num += char
			

	def addVertex(self, vertice):
        #Agrega un vertice al grafo
		self.grafo[vertice.value] = {}
 
	def delVertex(self, vertice):
        #Si el vertice esta en el grafo, lo remueve
		try:
			self.grafo.pop(vertice)
			return True
		except KeyError:
            #El vertice no estan en el grafo
			return False

	def isVertex(self, vertice):
        #Retorna true si el vertice esta en el grafo
		try:
			self.grafo[vertice.value]
			return True
		except KeyError:
			return False
 
	# def addEdge(self, vertice1, vertice2, arista):
        #Agrega una arista si los vertices existen
		# try:
			# self.grafo[vertice1][vertice2] = arista
			# self.grafo[vertice2][vertice1] = arista
			# print "V1: ",self.grafo[vertice1]
			# print "V2: ",self.grafo[vertice2]
			# return True
		# except KeyError:
			# print "Error al agregar arista"
            #Los vertices no estan en el grafo
			# return False
			
	def addEdge(self, edge):
        #Agrega una arista si los vertices existen
		try:
			self.grafo[edge.vertex1.value][edge.vertex2.value] = edge.weight
			self.grafo[edge.vertex2.value][edge.vertex1.value] = edge.weight
			print "V1: ",self.grafo[edge.vertex1.value]
			print "V2: ",self.grafo[edge.vertex2.value]
			return True
		except KeyError:
			print "Error al agregar arista"
            #Los vertices no estan en el grafo
			return False
 
	def delEdge(self, vertice1, vertice2):
        #Remueve la arista del grafo
		try:
			self.grafo[vertice][vertice2].pop()
			return True
		except KeyError:
            #Los vertices no estan en el grafo
			return False
            
	def getEdge(self, vertice1, vertice2):
		try:
			return self.grafo[vertice1][vertice2]
		except KeyError:
			#Los vertices no estan en el grafo
			print "Los vertices no estan en el grafo"
			return False
		     
	# def	getMST(self):
		# subtrees = UnionFind()
		# tree = []
		# edges = []
		  
		# for u in self.getAllVertex():
			# for v in self.getVecinos(u):
				##Agrego todas las aristas a un heap
				# heapq.heappush(edges, (self.getEdge(u,v),u,v))
		# print "Edges", edges
		# min = heapq.heappop(edges)
		# try:
			# while (min):
				# if subtrees[u] != subtrees[v]:
					# tree.append((u,v))
					# subtrees.union(u,v)
				# min = heapq.heappop(edges)
		# except IndexError:
			# return tree
			
	# Kruskal Definition
	# - create a forest F (a set of trees), where each vertex in the graph is a separate tree
	# - create a set S containing all the edges in the graph
	# - while S is nonempty and F is not yet spanning
	#	  remove an edge with minimum weight from S
	#	  if that edge connects two different trees, then add it to the forest, combining the trees, 
	# 		otherwise discard that edge.
	# - At the termination of the algorithm, the forest has only one component (ST).
	def kruskal(self):
		
	
		#for vertexs in getAllVertex()
			#for edges in getVecinos
		edges = []
		for u in self.getAllVertex():
			for v in self.getVecinos(u):
				heapq.heappush(edges, (self.getEdge(u,v),Edges(u,v,self.getEdge(u,v))) )
	
		T = []  #this contains all the edges in the tree
	
		#run makeset on all the vertices
	
		for vertex in self.getAllVertex():
			MakeSet(vertex)
	
		while edges:
			min_edge = heapq.heappop(edges)[1]
			if FindSet(min_edge.vertex1) is not FindSet(min_edge.vertex2):
				#perform a union and add this edge to the Tree
				T.append(min_edge)
				Union(min_edge.vertex1, min_edge.vertex2)
		return T
		#return True
		
	
	def getAllVertex(self):
		# Devuelve una lista con todos los vertices
		return self.grafo.keys()	
	
	def getAllEdges(self):
		edges = []
		for u in self.getAllVertex():
			for v in self.getVecinos(u):
				heapq.heappush(edges, Edges(u,v,self.getEdge(u,v)))
		return edges

	def getVecinos(self, vertex):
		try:
			return self.grafo[vertex]
		except KeyError:
			return False
    
